FPS24 G - 硬貨
硬貨$ 1,2,\cdots,L をそれぞれ何枚かずつ使う時の合計金額と通り数は$ (1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots (1+x^L+x^{2L}+\cdots) と表せる．
これを整理すれば$ P(x)=\prod_{k=1}^L \frac{1}{1-x^k} と書ける．この$ x^Nの係数を見ることで$ m=1の時は解けた．
$ mを1増やすと$ \prod_{k=2}^{L+1} \frac{1}{1-x^k}が求める式になるが，これは$ \frac{1-x}{1-x^{L+1}}P(x)として求められる．掛ける式と割る式が共にsparseなので愚直に計算するとlog factorがつかずにすむ．
掛ける方は自明．割る方は$ g(x)(1-x^k)=f(x)を満たす$ g(x)を求めることを考えると$ 0 \le i \le k-1の範囲では$ g_i=f_i, それ以上では $ g_i-g_{i-k}=f_iであることから導かれる．
コメント
早いライブラリがあれば通るのかな．